# 递归
# class Solution(object):
#     def verifyPreorder(self, preorder):
#         """
#         :type preorder: List[int]
#         :rtype: bool
#         """
#
#         def search(i, j):
#             if j - i <= 1:
#                 return True
#             else:
#                 k = i + 1
#                 flag = False
#                 while k <= j:
#                     if flag:
#                         if preorder[k] < preorder[i]:
#                             return False
#                     else:
#                         if preorder[k] > preorder[i]:
#                             mid = k
#                             flag = True
#                     k += 1
#                 if not flag:
#                     return search(i + 1, j)
#                 else:
#                     return search(i + 1, mid - 1) and search(mid, j)
#
#         return search(0, len(preorder) - 1)

# 栈
import collections


class Solution(object):
    def verifyPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: bool
        """
        min_value = 0
        stack = collections.deque([0])
        for i in range(1, len(preorder)):
            if preorder[i] < preorder[i - 1]:
                if preorder[i] < min_value:
                    return False
                stack.append(i)
            else:
                while stack and preorder[stack[-1]] < preorder[i]:
                    min_value = preorder[stack.pop()]
                stack.append(i)
        return True


data = Solution()
preorder = [5, 2, 6, 1, 3]
print(data.verifyPreorder(preorder))
